//
// Description: 5786. 可移除字符的最大数目
// Created by Loading on 2021/6/13.
//

#include <bits/stdc++.h>

using namespace std;

/* 典型的二分查找问题 */
int maximumRemovals(string s, string p, vector<int> &removable) {
    int low = 0, high = removable.size() - 1;
    //辅助函数，检查当前 k 是否符合要求
    auto check = [&](int k) {
        //参数传递为引用，使用临时变量 temp 复制 s，后续操作 temp，否则 s 会变化
        string temp = s;
        for (int i = 0; i <= k; ++i) {
            //用字符 '#' 模拟删除
            temp[removable[i]] = '#';
        }

        // 使用 find 遍历匹配，注意：index 的取值
        int index = -1;
        for (auto &c : p){
            index = temp.find(c, index + 1);
            if (index != string::npos) {
                continue;
            } else {
                return false;
            }
        }
        return true;

        //顺序遍历匹配
//        int i = 0, j = 0;
//        while (i < temp.size() && j < p.size()) {
//            if (temp[i] == p[j]) {
//                ++j;
//            }
//            ++i;
//        }
//        return j == p.size();
    };

    //二分查找
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (check(mid)) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return low;

    /* 暴力法，超时 */
//    for (int i = 0; i < removable.size(); ++i) {
//        if (p.size() > s.size() - i){
//            return i;
//        }
//        s[removable[i]] = '#';
//        int index = -1;
//        for (auto &c : p) {
//            index = s.find(c, index + 1);
//            if (index != string::npos) {
//                continue;
//            } else {
//                return i;
//            }
//        }
//    }
//
//    return removable.size();
}

int main() {
    string s = "abcab";
    string p = "abc";
    vector<int> removable = {0, 1, 2, 3, 4};
    cout << maximumRemovals(s, p, removable) << endl;
}